package com.itheima.algorithm.binarytree;

import java.util.Arrays;

/**
 * @author: TylerZhong
 * @description:
 * 根据前序中序遍历结果构造二叉树
 */
public class E09Leetcode105 {
    /**
     * preOrder = {1,2,4,3,6,7}
     * inOrder = {4,2,1,6,3,7}
     * @param preOrder
     * @param inOrder
     * @return
     */
    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0) {
            return null;
        }
        // 创建根节点
        int rootValue = preOrder[0];
        TreeNode node = new TreeNode(rootValue);
        // 区分左右子树
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i+1, inOrder.length);

                int[] preLeft = Arrays.copyOfRange(preOrder, 1, i+1);
                int[] preRight = Arrays.copyOfRange(preOrder, i + 1, inOrder.length);

                node.left = buildTree(preLeft, inLeft);
                node.right = buildTree(preRight, inRight);
                break;
            }
        }
        return node;
    }
}
